/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent.locks;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.LockSupport;

/**
 * A capability-based lock with three modes for controlling read/write
 * access.  The state of a StampedLock consists of a version and mode.
 * Lock acquisition methods return a stamp that represents and
 * controls access with respect to a lock state; "try" versions of
 * these methods may instead return the special value zero to
 * represent failure to acquire access. Lock release and conversion
 * methods require stamps as arguments, and fail if they do not match
 * the state of the lock. The three modes are:
 *
 * <ul>
 *
 * <li><b>Writing.</b> Method {@link #writeLock} possibly blocks
 * waiting for exclusive access, returning a stamp that can be used
 * in method {@link #unlockWrite} to release the lock. Untimed and
 * timed versions of {@code tryWriteLock} are also provided. When
 * the lock is held in write mode, no read locks may be obtained,
 * and all optimistic read validations will fail.  </li>
 *
 * <li><b>Reading.</b> Method {@link #readLock} possibly blocks
 * waiting for non-exclusive access, returning a stamp that can be
 * used in method {@link #unlockRead} to release the lock. Untimed
 * and timed versions of {@code tryReadLock} are also provided. </li>
 *
 * <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
 * returns a non-zero stamp only if the lock is not currently held
 * in write mode. Method {@link #validate} returns true if the lock
 * has not been acquired in write mode since obtaining a given
 * stamp.  This mode can be thought of as an extremely weak version
 * of a read-lock, that can be broken by a writer at any time.  The
 * use of optimistic mode for short read-only code segments often
 * reduces contention and improves throughput.  However, its use is
 * inherently fragile.  Optimistic read sections should only read
 * fields and hold them in local variables for later use after
 * validation. Fields read while in optimistic mode may be wildly
 * inconsistent, so usage applies only when you are familiar enough
 * with data representations to check consistency and/or repeatedly
 * invoke method {@code validate()}.  For example, such steps are
 * typically required when first reading an object or array
 * reference, and then accessing one of its fields, elements or
 * methods. </li>
 *
 * </ul>
 *
 * <p>This class also supports methods that conditionally provide
 * conversions across the three modes. For example, method {@link
 * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning
 * a valid write stamp if (1) already in writing mode (2) in reading
 * mode and there are no other readers or (3) in optimistic mode and
 * the lock is available. The forms of these methods are designed to
 * help reduce some of the code bloat that otherwise occurs in
 * retry-based designs.
 *
 * <p>StampedLocks are designed for use as internal utilities in the
 * development of thread-safe components. Their use relies on
 * knowledge of the internal properties of the data, objects, and
 * methods they are protecting.  They are not reentrant, so locked
 * bodies should not call other unknown methods that may try to
 * re-acquire locks (although you may pass a stamp to other methods
 * that can use or convert it).  The use of read lock modes relies on
 * the associated code sections being side-effect-free.  Unvalidated
 * optimistic read sections cannot call methods that are not known to
 * tolerate potential inconsistencies.  Stamps use finite
 * representations, and are not cryptographically secure (i.e., a
 * valid stamp may be guessable). Stamp values may recycle after (no
 * sooner than) one year of continuous operation. A stamp held without
 * use or validation for longer than this period may fail to validate
 * correctly.  StampedLocks are serializable, but always deserialize
 * into initial unlocked state, so they are not useful for remote
 * locking.
 *
 * <p>The scheduling policy of StampedLock does not consistently
 * prefer readers over writers or vice versa.  All "try" methods are
 * best-effort and do not necessarily conform to any scheduling or
 * fairness policy. A zero return from any "try" method for acquiring
 * or converting locks does not carry any information about the state
 * of the lock; a subsequent invocation may succeed.
 *
 * <p>Because it supports coordinated usage across multiple lock
 * modes, this class does not directly implement the {@link Lock} or
 * {@link ReadWriteLock} interfaces. However, a StampedLock may be
 * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link
 * #asReadWriteLock()} in applications requiring only the associated
 * set of functionality.
 *
 * <p><b>Sample Usage.</b> The following illustrates some usage idioms
 * in a class that maintains simple two-dimensional points. The sample
 * code illustrates some try/catch conventions even though they are
 * not strictly needed here because no exceptions can occur in their
 * bodies.<br>
 *
 * <pre>{@code
 * class Point {
 *   private double x, y;
 *   private final StampedLock sl = new StampedLock();
 *
 *   void move(double deltaX, double deltaY) { // an exclusively locked method
 *     long stamp = sl.writeLock();
 *     try {
 *       x += deltaX;
 *       y += deltaY;
 *     } finally {
 *       sl.unlockWrite(stamp);
 *     }
 *   }
 *
 *   double distanceFromOrigin() { // A read-only method
 *     long stamp = sl.tryOptimisticRead();
 *     double currentX = x, currentY = y;
 *     if (!sl.validate(stamp)) {
 *        stamp = sl.readLock();
 *        try {
 *          currentX = x;
 *          currentY = y;
 *        } finally {
 *           sl.unlockRead(stamp);
 *        }
 *     }
 *     return Math.sqrt(currentX * currentX + currentY * currentY);
 *   }
 *
 *   void moveIfAtOrigin(double newX, double newY) { // upgrade
 *     // Could instead start with optimistic, not read mode
 *     long stamp = sl.readLock();
 *     try {
 *       while (x == 0.0 && y == 0.0) {
 *         long ws = sl.tryConvertToWriteLock(stamp);
 *         if (ws != 0L) {
 *           stamp = ws;
 *           x = newX;
 *           y = newY;
 *           break;
 *         }
 *         else {
 *           sl.unlockRead(stamp);
 *           stamp = sl.writeLock();
 *         }
 *       }
 *     } finally {
 *       sl.unlock(stamp);
 *     }
 *   }
 * }}</pre>
 *
 * @author Doug Lea
 * @since 1.8
 */
public class StampedLock implements java.io.Serializable {
    /*
     * Algorithmic notes:
     *
     * The design employs elements of Sequence locks
     * (as used in linux kernels; see Lameter's
     * http://www.lameter.com/gelato2005.pdf
     * and elsewhere; see
     * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
     * and Ordered RW locks (see Shirako et al
     * http://dl.acm.org/citation.cfm?id=2312015)
     *
     * Conceptually, the primary state of the lock includes a sequence
     * number that is odd when write-locked and even otherwise.
     * However, this is offset by a reader count that is non-zero when
     * read-locked.  The read count is ignored when validating
     * "optimistic" seqlock-reader-style stamps.  Because we must use
     * a small finite number of bits (currently 7) for readers, a
     * supplementary reader overflow word is used when the number of
     * readers exceeds the count field. We do this by treating the max
     * reader count value (RBITS) as a spinlock protecting overflow
     * updates.
     *
     * Waiters use a modified form of CLH lock used in
     * AbstractQueuedSynchronizer (see its internal documentation for
     * a fuller account), where each node is tagged (field mode) as
     * either a reader or writer. Sets of waiting readers are grouped
     * (linked) under a common node (field cowait) so act as a single
     * node with respect to most CLH mechanics.  By virtue of the
     * queue structure, wait nodes need not actually carry sequence
     * numbers; we know each is greater than its predecessor.  This
     * simplifies the scheduling policy to a mainly-FIFO scheme that
     * incorporates elements of Phase-Fair locks (see Brandenburg &
     * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
     * particular, we use the phase-fair anti-barging rule: If an
     * incoming reader arrives while read lock is held but there is a
     * queued writer, this incoming reader is queued.  (This rule is
     * responsible for some of the complexity of method acquireRead,
     * but without it, the lock becomes highly unfair.) Method release
     * does not (and sometimes cannot) itself wake up cowaiters. This
     * is done by the primary thread, but helped by any other threads
     * with nothing better to do in methods acquireRead and
     * acquireWrite.
     *
     * These rules apply to threads actually queued. All tryLock forms
     * opportunistically try to acquire locks regardless of preference
     * rules, and so may "barge" their way in.  Randomized spinning is
     * used in the acquire methods to reduce (increasingly expensive)
     * context switching while also avoiding sustained memory
     * thrashing among many threads.  We limit spins to the head of
     * queue. A thread spin-waits up to SPINS times (where each
     * iteration decreases spin count with 50% probability) before
     * blocking. If, upon wakening it fails to obtain lock, and is
     * still (or becomes) the first waiting thread (which indicates
     * that some other thread barged and obtained lock), it escalates
     * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
     * continually losing to barging threads.
     *
     * Nearly all of these mechanics are carried out in methods
     * acquireWrite and acquireRead, that, as typical of such code,
     * sprawl out because actions and retries rely on consistent sets
     * of locally cached reads.
     *
     * As noted in Boehm's paper (above), sequence validation (mainly
     * method validate()) requires stricter ordering rules than apply
     * to normal volatile reads (of "state").  To force orderings of
     * reads before a validation and the validation itself in those
     * cases where this is not already forced, we use
     * Unsafe.loadFence.
     *
     * The memory layout keeps lock state and queue pointers together
     * (normally on the same cache line). This usually works well for
     * read-mostly loads. In most other cases, the natural tendency of
     * adaptive-spin CLH locks to reduce memory contention lessens
     * motivation to further spread out contended locations, but might
     * be subject to future improvements.
     */

  private static final long serialVersionUID = -6001602636862214147L;

  /**
   * Number of processors, for spin control
   */
  private static final int NCPU = Runtime.getRuntime().availableProcessors();

  /**
   * Maximum number of retries before enqueuing on acquisition
   */
  private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;

  /**
   * Maximum number of retries before blocking at head on acquisition
   */
  private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;

  /**
   * Maximum number of retries before re-blocking
   */
  private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;

  /**
   * The period for yielding when waiting for overflow spinlock
   */
  private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1

  /**
   * The number of bits to use for reader count before overflowing
   */
  private static final int LG_READERS = 7;

  // Values for lock state and stamp operations
  private static final long RUNIT = 1L;
  private static final long WBIT = 1L << LG_READERS;
  private static final long RBITS = WBIT - 1L;
  private static final long RFULL = RBITS - 1L;
  private static final long ABITS = RBITS | WBIT;
  private static final long SBITS = ~RBITS; // note overlap with ABITS

  // Initial value for lock state; avoid failure value zero
  private static final long ORIGIN = WBIT << 1;

  // Special value from cancelled acquire methods so caller can throw IE
  private static final long INTERRUPTED = 1L;

  // Values for node status; order matters
  private static final int WAITING = -1;
  private static final int CANCELLED = 1;

  // Modes for nodes (int not boolean to allow arithmetic)
  private static final int RMODE = 0;
  private static final int WMODE = 1;

  /**
   * Wait nodes
   */
  static final class WNode {

    volatile WNode prev;
    volatile WNode next;
    volatile WNode cowait;    // list of linked readers
    volatile Thread thread;   // non-null while possibly parked
    volatile int status;      // 0, WAITING, or CANCELLED
    final int mode;           // RMODE or WMODE

    WNode(int m, WNode p) {
      mode = m;
      prev = p;
    }
  }

  /**
   * Head of CLH queue
   */
  private transient volatile WNode whead;
  /**
   * Tail (last) of CLH queue
   */
  private transient volatile WNode wtail;

  // views
  transient ReadLockView readLockView;
  transient WriteLockView writeLockView;
  transient ReadWriteLockView readWriteLockView;

  /**
   * Lock sequence/state
   */
  private transient volatile long state;
  /**
   * extra reader count when state read count saturated
   */
  private transient int readerOverflow;

  /**
   * Creates a new lock, initially in unlocked state.
   */
  public StampedLock() {
    state = ORIGIN;
  }

  /**
   * Exclusively acquires the lock, blocking if necessary
   * until available.
   *
   * @return a stamp that can be used to unlock or convert mode
   */
  public long writeLock() {
    long s, next;  // bypass acquireWrite in fully unlocked case only
    return ((((s = state) & ABITS) == 0L &&
        U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
        next : acquireWrite(false, 0L));
  }

  /**
   * Exclusively acquires the lock if it is immediately available.
   *
   * @return a stamp that can be used to unlock or convert mode, or zero if the lock is not
   * available
   */
  public long tryWriteLock() {
    long s, next;
    return ((((s = state) & ABITS) == 0L &&
        U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
        next : 0L);
  }

  /**
   * Exclusively acquires the lock if it is available within the
   * given time and the current thread has not been interrupted.
   * Behavior under timeout and interruption matches that specified
   * for method {@link Lock#tryLock(long, TimeUnit)}.
   *
   * @param time the maximum time to wait for the lock
   * @param unit the time unit of the {@code time} argument
   * @return a stamp that can be used to unlock or convert mode, or zero if the lock is not
   * available
   * @throws InterruptedException if the current thread is interrupted before acquiring the lock
   */
  public long tryWriteLock(long time, TimeUnit unit)
      throws InterruptedException {
    long nanos = unit.toNanos(time);
    if (!Thread.interrupted()) {
      long next, deadline;
      if ((next = tryWriteLock()) != 0L) {
        return next;
      }
      if (nanos <= 0L) {
        return 0L;
      }
      if ((deadline = System.nanoTime() + nanos) == 0L) {
        deadline = 1L;
      }
      if ((next = acquireWrite(true, deadline)) != INTERRUPTED) {
        return next;
      }
    }
    throw new InterruptedException();
  }

  /**
   * Exclusively acquires the lock, blocking if necessary
   * until available or the current thread is interrupted.
   * Behavior under interruption matches that specified
   * for method {@link Lock#lockInterruptibly()}.
   *
   * @return a stamp that can be used to unlock or convert mode
   * @throws InterruptedException if the current thread is interrupted before acquiring the lock
   */
  public long writeLockInterruptibly() throws InterruptedException {
    long next;
    if (!Thread.interrupted() &&
        (next = acquireWrite(true, 0L)) != INTERRUPTED) {
      return next;
    }
    throw new InterruptedException();
  }

  /**
   * Non-exclusively acquires the lock, blocking if necessary
   * until available.
   *
   * @return a stamp that can be used to unlock or convert mode
   */
  public long readLock() {
    long s = state, next;  // bypass acquireRead on common uncontended case
    return ((whead == wtail && (s & ABITS) < RFULL &&
        U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
        next : acquireRead(false, 0L));
  }

  /**
   * Non-exclusively acquires the lock if it is immediately available.
   *
   * @return a stamp that can be used to unlock or convert mode, or zero if the lock is not
   * available
   */
  public long tryReadLock() {
    for (; ; ) {
      long s, m, next;
      if ((m = (s = state) & ABITS) == WBIT) {
        return 0L;
      } else if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) {
          return next;
        }
      } else if ((next = tryIncReaderOverflow(s)) != 0L) {
        return next;
      }
    }
  }

  /**
   * Non-exclusively acquires the lock if it is available within the
   * given time and the current thread has not been interrupted.
   * Behavior under timeout and interruption matches that specified
   * for method {@link Lock#tryLock(long, TimeUnit)}.
   *
   * @param time the maximum time to wait for the lock
   * @param unit the time unit of the {@code time} argument
   * @return a stamp that can be used to unlock or convert mode, or zero if the lock is not
   * available
   * @throws InterruptedException if the current thread is interrupted before acquiring the lock
   */
  public long tryReadLock(long time, TimeUnit unit)
      throws InterruptedException {
    long s, m, next, deadline;
    long nanos = unit.toNanos(time);
    if (!Thread.interrupted()) {
      if ((m = (s = state) & ABITS) != WBIT) {
        if (m < RFULL) {
          if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) {
            return next;
          }
        } else if ((next = tryIncReaderOverflow(s)) != 0L) {
          return next;
        }
      }
      if (nanos <= 0L) {
        return 0L;
      }
      if ((deadline = System.nanoTime() + nanos) == 0L) {
        deadline = 1L;
      }
      if ((next = acquireRead(true, deadline)) != INTERRUPTED) {
        return next;
      }
    }
    throw new InterruptedException();
  }

  /**
   * Non-exclusively acquires the lock, blocking if necessary
   * until available or the current thread is interrupted.
   * Behavior under interruption matches that specified
   * for method {@link Lock#lockInterruptibly()}.
   *
   * @return a stamp that can be used to unlock or convert mode
   * @throws InterruptedException if the current thread is interrupted before acquiring the lock
   */
  public long readLockInterruptibly() throws InterruptedException {
    long next;
    if (!Thread.interrupted() &&
        (next = acquireRead(true, 0L)) != INTERRUPTED) {
      return next;
    }
    throw new InterruptedException();
  }

  /**
   * Returns a stamp that can later be validated, or zero
   * if exclusively locked.
   *
   * @return a stamp, or zero if exclusively locked
   */
  public long tryOptimisticRead() {
    long s;
    return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;
  }

  /**
   * Returns true if the lock has not been exclusively acquired
   * since issuance of the given stamp. Always returns false if the
   * stamp is zero. Always returns true if the stamp represents a
   * currently held lock. Invoking this method with a value not
   * obtained from {@link #tryOptimisticRead} or a locking method
   * for this lock has no defined effect or result.
   *
   * @param stamp a stamp
   * @return {@code true} if the lock has not been exclusively acquired since issuance of the given
   * stamp; else false
   */
  public boolean validate(long stamp) {
    U.loadFence();
    return (stamp & SBITS) == (state & SBITS);
  }

  /**
   * If the lock state matches the given stamp, releases the
   * exclusive lock.
   *
   * @param stamp a stamp returned by a write-lock operation
   * @throws IllegalMonitorStateException if the stamp does not match the current state of this
   * lock
   */
  public void unlockWrite(long stamp) {
    WNode h;
    if (state != stamp || (stamp & WBIT) == 0L) {
      throw new IllegalMonitorStateException();
    }
    state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
    if ((h = whead) != null && h.status != 0) {
      release(h);
    }
  }

  /**
   * If the lock state matches the given stamp, releases the
   * non-exclusive lock.
   *
   * @param stamp a stamp returned by a read-lock operation
   * @throws IllegalMonitorStateException if the stamp does not match the current state of this
   * lock
   */
  public void unlockRead(long stamp) {
    long s, m;
    WNode h;
    for (; ; ) {
      if (((s = state) & SBITS) != (stamp & SBITS) ||
          (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT) {
        throw new IllegalMonitorStateException();
      }
      if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
          if (m == RUNIT && (h = whead) != null && h.status != 0) {
            release(h);
          }
          break;
        }
      } else if (tryDecReaderOverflow(s) != 0L) {
        break;
      }
    }
  }

  /**
   * If the lock state matches the given stamp, releases the
   * corresponding mode of the lock.
   *
   * @param stamp a stamp returned by a lock operation
   * @throws IllegalMonitorStateException if the stamp does not match the current state of this
   * lock
   */
  public void unlock(long stamp) {
    long a = stamp & ABITS, m, s;
    WNode h;
    while (((s = state) & SBITS) == (stamp & SBITS)) {
      if ((m = s & ABITS) == 0L) {
        break;
      } else if (m == WBIT) {
        if (a != m) {
          break;
        }
        state = (s += WBIT) == 0L ? ORIGIN : s;
        if ((h = whead) != null && h.status != 0) {
          release(h);
        }
        return;
      } else if (a == 0L || a >= WBIT) {
        break;
      } else if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
          if (m == RUNIT && (h = whead) != null && h.status != 0) {
            release(h);
          }
          return;
        }
      } else if (tryDecReaderOverflow(s) != 0L) {
        return;
      }
    }
    throw new IllegalMonitorStateException();
  }

  /**
   * If the lock state matches the given stamp, performs one of
   * the following actions. If the stamp represents holding a write
   * lock, returns it.  Or, if a read lock, if the write lock is
   * available, releases the read lock and returns a write stamp.
   * Or, if an optimistic read, returns a write stamp only if
   * immediately available. This method returns zero in all other
   * cases.
   *
   * @param stamp a stamp
   * @return a valid write stamp, or zero on failure
   */
  public long tryConvertToWriteLock(long stamp) {
    long a = stamp & ABITS, m, s, next;
    while (((s = state) & SBITS) == (stamp & SBITS)) {
      if ((m = s & ABITS) == 0L) {
        if (a != 0L) {
          break;
        }
        if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) {
          return next;
        }
      } else if (m == WBIT) {
        if (a != m) {
          break;
        }
        return stamp;
      } else if (m == RUNIT && a != 0L) {
        if (U.compareAndSwapLong(this, STATE, s,
            next = s - RUNIT + WBIT)) {
          return next;
        }
      } else {
        break;
      }
    }
    return 0L;
  }

  /**
   * If the lock state matches the given stamp, performs one of
   * the following actions. If the stamp represents holding a write
   * lock, releases it and obtains a read lock.  Or, if a read lock,
   * returns it. Or, if an optimistic read, acquires a read lock and
   * returns a read stamp only if immediately available. This method
   * returns zero in all other cases.
   *
   * @param stamp a stamp
   * @return a valid read stamp, or zero on failure
   */
  public long tryConvertToReadLock(long stamp) {
    long a = stamp & ABITS, m, s, next;
    WNode h;
    while (((s = state) & SBITS) == (stamp & SBITS)) {
      if ((m = s & ABITS) == 0L) {
        if (a != 0L) {
          break;
        } else if (m < RFULL) {
          if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) {
            return next;
          }
        } else if ((next = tryIncReaderOverflow(s)) != 0L) {
          return next;
        }
      } else if (m == WBIT) {
        if (a != m) {
          break;
        }
        state = next = s + (WBIT + RUNIT);
        if ((h = whead) != null && h.status != 0) {
          release(h);
        }
        return next;
      } else if (a != 0L && a < WBIT) {
        return stamp;
      } else {
        break;
      }
    }
    return 0L;
  }

  /**
   * If the lock state matches the given stamp then, if the stamp
   * represents holding a lock, releases it and returns an
   * observation stamp.  Or, if an optimistic read, returns it if
   * validated. This method returns zero in all other cases, and so
   * may be useful as a form of "tryUnlock".
   *
   * @param stamp a stamp
   * @return a valid optimistic read stamp, or zero on failure
   */
  public long tryConvertToOptimisticRead(long stamp) {
    long a = stamp & ABITS, m, s, next;
    WNode h;
    U.loadFence();
    for (; ; ) {
      if (((s = state) & SBITS) != (stamp & SBITS)) {
        break;
      }
      if ((m = s & ABITS) == 0L) {
        if (a != 0L) {
          break;
        }
        return s;
      } else if (m == WBIT) {
        if (a != m) {
          break;
        }
        state = next = (s += WBIT) == 0L ? ORIGIN : s;
        if ((h = whead) != null && h.status != 0) {
          release(h);
        }
        return next;
      } else if (a == 0L || a >= WBIT) {
        break;
      } else if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
          if (m == RUNIT && (h = whead) != null && h.status != 0) {
            release(h);
          }
          return next & SBITS;
        }
      } else if ((next = tryDecReaderOverflow(s)) != 0L) {
        return next & SBITS;
      }
    }
    return 0L;
  }

  /**
   * Releases the write lock if it is held, without requiring a
   * stamp value. This method may be useful for recovery after
   * errors.
   *
   * @return {@code true} if the lock was held, else false
   */
  public boolean tryUnlockWrite() {
    long s;
    WNode h;
    if (((s = state) & WBIT) != 0L) {
      state = (s += WBIT) == 0L ? ORIGIN : s;
      if ((h = whead) != null && h.status != 0) {
        release(h);
      }
      return true;
    }
    return false;
  }

  /**
   * Releases one hold of the read lock if it is held, without
   * requiring a stamp value. This method may be useful for recovery
   * after errors.
   *
   * @return {@code true} if the read lock was held, else false
   */
  public boolean tryUnlockRead() {
    long s, m;
    WNode h;
    while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
      if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
          if (m == RUNIT && (h = whead) != null && h.status != 0) {
            release(h);
          }
          return true;
        }
      } else if (tryDecReaderOverflow(s) != 0L) {
        return true;
      }
    }
    return false;
  }

  // status monitoring methods

  /**
   * Returns combined state-held and overflow read count for given
   * state s.
   */
  private int getReadLockCount(long s) {
    long readers;
    if ((readers = s & RBITS) >= RFULL) {
      readers = RFULL + readerOverflow;
    }
    return (int) readers;
  }

  /**
   * Returns {@code true} if the lock is currently held exclusively.
   *
   * @return {@code true} if the lock is currently held exclusively
   */
  public boolean isWriteLocked() {
    return (state & WBIT) != 0L;
  }

  /**
   * Returns {@code true} if the lock is currently held non-exclusively.
   *
   * @return {@code true} if the lock is currently held non-exclusively
   */
  public boolean isReadLocked() {
    return (state & RBITS) != 0L;
  }

  /**
   * Queries the number of read locks held for this lock. This
   * method is designed for use in monitoring system state, not for
   * synchronization control.
   *
   * @return the number of read locks held
   */
  public int getReadLockCount() {
    return getReadLockCount(state);
  }

  /**
   * Returns a string identifying this lock, as well as its lock
   * state.  The state, in brackets, includes the String {@code
   * "Unlocked"} or the String {@code "Write-locked"} or the String
   * {@code "Read-locks:"} followed by the current number of
   * read-locks held.
   *
   * @return a string identifying this lock, as well as its lock state
   */
  public String toString() {
    long s = state;
    return super.toString() +
        ((s & ABITS) == 0L ? "[Unlocked]" :
            (s & WBIT) != 0L ? "[Write-locked]" :
                "[Read-locks:" + getReadLockCount(s) + "]");
  }

  // views

  /**
   * Returns a plain {@link Lock} view of this StampedLock in which
   * the {@link Lock#lock} method is mapped to {@link #readLock},
   * and similarly for other methods. The returned Lock does not
   * support a {@link Condition}; method {@link
   * Lock#newCondition()} throws {@code
   * UnsupportedOperationException}.
   *
   * @return the lock
   */
  public Lock asReadLock() {
    ReadLockView v;
    return ((v = readLockView) != null ? v :
        (readLockView = new ReadLockView()));
  }

  /**
   * Returns a plain {@link Lock} view of this StampedLock in which
   * the {@link Lock#lock} method is mapped to {@link #writeLock},
   * and similarly for other methods. The returned Lock does not
   * support a {@link Condition}; method {@link
   * Lock#newCondition()} throws {@code
   * UnsupportedOperationException}.
   *
   * @return the lock
   */
  public Lock asWriteLock() {
    WriteLockView v;
    return ((v = writeLockView) != null ? v :
        (writeLockView = new WriteLockView()));
  }

  /**
   * Returns a {@link ReadWriteLock} view of this StampedLock in
   * which the {@link ReadWriteLock#readLock()} method is mapped to
   * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
   * {@link #asWriteLock()}.
   *
   * @return the lock
   */
  public ReadWriteLock asReadWriteLock() {
    ReadWriteLockView v;
    return ((v = readWriteLockView) != null ? v :
        (readWriteLockView = new ReadWriteLockView()));
  }

  // view classes

  final class ReadLockView implements Lock {

    public void lock() {
      readLock();
    }

    public void lockInterruptibly() throws InterruptedException {
      readLockInterruptibly();
    }

    public boolean tryLock() {
      return tryReadLock() != 0L;
    }

    public boolean tryLock(long time, TimeUnit unit)
        throws InterruptedException {
      return tryReadLock(time, unit) != 0L;
    }

    public void unlock() {
      unstampedUnlockRead();
    }

    public Condition newCondition() {
      throw new UnsupportedOperationException();
    }
  }

  final class WriteLockView implements Lock {

    public void lock() {
      writeLock();
    }

    public void lockInterruptibly() throws InterruptedException {
      writeLockInterruptibly();
    }

    public boolean tryLock() {
      return tryWriteLock() != 0L;
    }

    public boolean tryLock(long time, TimeUnit unit)
        throws InterruptedException {
      return tryWriteLock(time, unit) != 0L;
    }

    public void unlock() {
      unstampedUnlockWrite();
    }

    public Condition newCondition() {
      throw new UnsupportedOperationException();
    }
  }

  final class ReadWriteLockView implements ReadWriteLock {

    public Lock readLock() {
      return asReadLock();
    }

    public Lock writeLock() {
      return asWriteLock();
    }
  }

  // Unlock methods without stamp argument checks for view classes.
  // Needed because view-class lock methods throw away stamps.

  final void unstampedUnlockWrite() {
    WNode h;
    long s;
    if (((s = state) & WBIT) == 0L) {
      throw new IllegalMonitorStateException();
    }
    state = (s += WBIT) == 0L ? ORIGIN : s;
    if ((h = whead) != null && h.status != 0) {
      release(h);
    }
  }

  final void unstampedUnlockRead() {
    for (; ; ) {
      long s, m;
      WNode h;
      if ((m = (s = state) & ABITS) == 0L || m >= WBIT) {
        throw new IllegalMonitorStateException();
      } else if (m < RFULL) {
        if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
          if (m == RUNIT && (h = whead) != null && h.status != 0) {
            release(h);
          }
          break;
        }
      } else if (tryDecReaderOverflow(s) != 0L) {
        break;
      }
    }
  }

  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    state = ORIGIN; // reset to unlocked state
  }

  // internals

  /**
   * Tries to increment readerOverflow by first setting state
   * access bits value to RBITS, indicating hold of spinlock,
   * then updating, then releasing.
   *
   * @param s a reader overflow stamp: (s & ABITS) >= RFULL
   * @return new stamp on success, else zero
   */
  private long tryIncReaderOverflow(long s) {
    // assert (s & ABITS) >= RFULL;
    if ((s & ABITS) == RFULL) {
      if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
        ++readerOverflow;
        state = s;
        return s;
      }
    } else if ((LockSupport.nextSecondarySeed() &
        OVERFLOW_YIELD_RATE) == 0) {
      Thread.yield();
    }
    return 0L;
  }

  /**
   * Tries to decrement readerOverflow.
   *
   * @param s a reader overflow stamp: (s & ABITS) >= RFULL
   * @return new stamp on success, else zero
   */
  private long tryDecReaderOverflow(long s) {
    // assert (s & ABITS) >= RFULL;
    if ((s & ABITS) == RFULL) {
      if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
        int r;
        long next;
        if ((r = readerOverflow) > 0) {
          readerOverflow = r - 1;
          next = s;
        } else {
          next = s - RUNIT;
        }
        state = next;
        return next;
      }
    } else if ((LockSupport.nextSecondarySeed() &
        OVERFLOW_YIELD_RATE) == 0) {
      Thread.yield();
    }
    return 0L;
  }

  /**
   * Wakes up the successor of h (normally whead). This is normally
   * just h.next, but may require traversal from wtail if next
   * pointers are lagging. This may fail to wake up an acquiring
   * thread when one or more have been cancelled, but the cancel
   * methods themselves provide extra safeguards to ensure liveness.
   */
  private void release(WNode h) {
    if (h != null) {
      WNode q;
      Thread w;
      U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
      if ((q = h.next) == null || q.status == CANCELLED) {
        for (WNode t = wtail; t != null && t != h; t = t.prev) {
          if (t.status <= 0) {
            q = t;
          }
        }
      }
      if (q != null && (w = q.thread) != null) {
        U.unpark(w);
      }
    }
  }

  /**
   * See above for explanation.
   *
   * @param interruptible true if should check interrupts and if so return INTERRUPTED
   * @param deadline if nonzero, the System.nanoTime value to timeout at (and return zero)
   * @return next state, or INTERRUPTED
   */
  private long acquireWrite(boolean interruptible, long deadline) {
    WNode node = null, p;
    for (int spins = -1; ; ) { // spin while enqueuing
      long m, s, ns;
      if ((m = (s = state) & ABITS) == 0L) {
        if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
          return ns;
        }
      } else if (spins < 0) {
        spins = (m == WBIT && wtail == whead) ? SPINS : 0;
      } else if (spins > 0) {
        if (LockSupport.nextSecondarySeed() >= 0) {
          --spins;
        }
      } else if ((p = wtail) == null) { // initialize queue
        WNode hd = new WNode(WMODE, null);
        if (U.compareAndSwapObject(this, WHEAD, null, hd)) {
          wtail = hd;
        }
      } else if (node == null) {
        node = new WNode(WMODE, p);
      } else if (node.prev != p) {
        node.prev = p;
      } else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
        p.next = node;
        break;
      }
    }

    for (int spins = -1; ; ) {
      WNode h, np, pp;
      int ps;
      if ((h = whead) == p) {
        if (spins < 0) {
          spins = HEAD_SPINS;
        } else if (spins < MAX_HEAD_SPINS) {
          spins <<= 1;
        }
        for (int k = spins; ; ) { // spin at head
          long s, ns;
          if (((s = state) & ABITS) == 0L) {
            if (U.compareAndSwapLong(this, STATE, s,
                ns = s + WBIT)) {
              whead = node;
              node.prev = null;
              return ns;
            }
          } else if (LockSupport.nextSecondarySeed() >= 0 &&
              --k <= 0) {
            break;
          }
        }
      } else if (h != null) { // help release stale waiters
        WNode c;
        Thread w;
        while ((c = h.cowait) != null) {
          if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
              (w = c.thread) != null) {
            U.unpark(w);
          }
        }
      }
      if (whead == h) {
        if ((np = node.prev) != p) {
          if (np != null) {
            (p = np).next = node;   // stale
          }
        } else if ((ps = p.status) == 0) {
          U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
        } else if (ps == CANCELLED) {
          if ((pp = p.prev) != null) {
            node.prev = pp;
            pp.next = node;
          }
        } else {
          long time; // 0 argument to park means no timeout
          if (deadline == 0L) {
            time = 0L;
          } else if ((time = deadline - System.nanoTime()) <= 0L) {
            return cancelWaiter(node, node, false);
          }
          Thread wt = Thread.currentThread();
          U.putObject(wt, PARKBLOCKER, this);
          node.thread = wt;
          if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&
              whead == h && node.prev == p) {
            U.park(false, time);  // emulate LockSupport.park
          }
          node.thread = null;
          U.putObject(wt, PARKBLOCKER, null);
          if (interruptible && Thread.interrupted()) {
            return cancelWaiter(node, node, true);
          }
        }
      }
    }
  }

  /**
   * See above for explanation.
   *
   * @param interruptible true if should check interrupts and if so return INTERRUPTED
   * @param deadline if nonzero, the System.nanoTime value to timeout at (and return zero)
   * @return next state, or INTERRUPTED
   */
  private long acquireRead(boolean interruptible, long deadline) {
    WNode node = null, p;
    for (int spins = -1; ; ) {
      WNode h;
      if ((h = whead) == (p = wtail)) {
        for (long m, s, ns; ; ) {
          if ((m = (s = state) & ABITS) < RFULL ?
              U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
              (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
            return ns;
          } else if (m >= WBIT) {
            if (spins > 0) {
              if (LockSupport.nextSecondarySeed() >= 0) {
                --spins;
              }
            } else {
              if (spins == 0) {
                WNode nh = whead, np = wtail;
                if ((nh == h && np == p) || (h = nh) != (p = np)) {
                  break;
                }
              }
              spins = SPINS;
            }
          }
        }
      }
      if (p == null) { // initialize queue
        WNode hd = new WNode(WMODE, null);
        if (U.compareAndSwapObject(this, WHEAD, null, hd)) {
          wtail = hd;
        }
      } else if (node == null) {
        node = new WNode(RMODE, p);
      } else if (h == p || p.mode != RMODE) {
        if (node.prev != p) {
          node.prev = p;
        } else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
          p.next = node;
          break;
        }
      } else if (!U.compareAndSwapObject(p, WCOWAIT,
          node.cowait = p.cowait, node)) {
        node.cowait = null;
      } else {
        for (; ; ) {
          WNode pp, c;
          Thread w;
          if ((h = whead) != null && (c = h.cowait) != null &&
              U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
              (w = c.thread) != null) // help release
          {
            U.unpark(w);
          }
          if (h == (pp = p.prev) || h == p || pp == null) {
            long m, s, ns;
            do {
              if ((m = (s = state) & ABITS) < RFULL ?
                  U.compareAndSwapLong(this, STATE, s,
                      ns = s + RUNIT) :
                  (m < WBIT &&
                      (ns = tryIncReaderOverflow(s)) != 0L)) {
                return ns;
              }
            } while (m < WBIT);
          }
          if (whead == h && p.prev == pp) {
            long time;
            if (pp == null || h == p || p.status > 0) {
              node = null; // throw away
              break;
            }
            if (deadline == 0L) {
              time = 0L;
            } else if ((time = deadline - System.nanoTime()) <= 0L) {
              return cancelWaiter(node, p, false);
            }
            Thread wt = Thread.currentThread();
            U.putObject(wt, PARKBLOCKER, this);
            node.thread = wt;
            if ((h != pp || (state & ABITS) == WBIT) &&
                whead == h && p.prev == pp) {
              U.park(false, time);
            }
            node.thread = null;
            U.putObject(wt, PARKBLOCKER, null);
            if (interruptible && Thread.interrupted()) {
              return cancelWaiter(node, p, true);
            }
          }
        }
      }
    }

    for (int spins = -1; ; ) {
      WNode h, np, pp;
      int ps;
      if ((h = whead) == p) {
        if (spins < 0) {
          spins = HEAD_SPINS;
        } else if (spins < MAX_HEAD_SPINS) {
          spins <<= 1;
        }
        for (int k = spins; ; ) { // spin at head
          long m, s, ns;
          if ((m = (s = state) & ABITS) < RFULL ?
              U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
              (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
            WNode c;
            Thread w;
            whead = node;
            node.prev = null;
            while ((c = node.cowait) != null) {
              if (U.compareAndSwapObject(node, WCOWAIT,
                  c, c.cowait) &&
                  (w = c.thread) != null) {
                U.unpark(w);
              }
            }
            return ns;
          } else if (m >= WBIT &&
              LockSupport.nextSecondarySeed() >= 0 && --k <= 0) {
            break;
          }
        }
      } else if (h != null) {
        WNode c;
        Thread w;
        while ((c = h.cowait) != null) {
          if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
              (w = c.thread) != null) {
            U.unpark(w);
          }
        }
      }
      if (whead == h) {
        if ((np = node.prev) != p) {
          if (np != null) {
            (p = np).next = node;   // stale
          }
        } else if ((ps = p.status) == 0) {
          U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
        } else if (ps == CANCELLED) {
          if ((pp = p.prev) != null) {
            node.prev = pp;
            pp.next = node;
          }
        } else {
          long time;
          if (deadline == 0L) {
            time = 0L;
          } else if ((time = deadline - System.nanoTime()) <= 0L) {
            return cancelWaiter(node, node, false);
          }
          Thread wt = Thread.currentThread();
          U.putObject(wt, PARKBLOCKER, this);
          node.thread = wt;
          if (p.status < 0 &&
              (p != h || (state & ABITS) == WBIT) &&
              whead == h && node.prev == p) {
            U.park(false, time);
          }
          node.thread = null;
          U.putObject(wt, PARKBLOCKER, null);
          if (interruptible && Thread.interrupted()) {
            return cancelWaiter(node, node, true);
          }
        }
      }
    }
  }

  /**
   * If node non-null, forces cancel status and unsplices it from
   * queue if possible and wakes up any cowaiters (of the node, or
   * group, as applicable), and in any case helps release current
   * first waiter if lock is free. (Calling with null arguments
   * serves as a conditional form of release, which is not currently
   * needed but may be needed under possible future cancellation
   * policies). This is a variant of cancellation methods in
   * AbstractQueuedSynchronizer (see its detailed explanation in AQS
   * internal documentation).
   *
   * @param node if nonnull, the waiter
   * @param group either node or the group node is cowaiting with
   * @param interrupted if already interrupted
   * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
   */
  private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
    if (node != null && group != null) {
      Thread w;
      node.status = CANCELLED;
      // unsplice cancelled nodes from group
      for (WNode p = group, q; (q = p.cowait) != null; ) {
        if (q.status == CANCELLED) {
          U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
          p = group; // restart
        } else {
          p = q;
        }
      }
      if (group == node) {
        for (WNode r = group.cowait; r != null; r = r.cowait) {
          if ((w = r.thread) != null) {
            U.unpark(w);       // wake up uncancelled co-waiters
          }
        }
        for (WNode pred = node.prev; pred != null; ) { // unsplice
          WNode succ, pp;        // find valid successor
          while ((succ = node.next) == null ||
              succ.status == CANCELLED) {
            WNode q = null;    // find successor the slow way
            for (WNode t = wtail; t != null && t != node; t = t.prev) {
              if (t.status != CANCELLED) {
                q = t;     // don't link if succ cancelled
              }
            }
            if (succ == q ||   // ensure accurate successor
                U.compareAndSwapObject(node, WNEXT,
                    succ, succ = q)) {
              if (succ == null && node == wtail) {
                U.compareAndSwapObject(this, WTAIL, node, pred);
              }
              break;
            }
          }
          if (pred.next == node) // unsplice pred link
          {
            U.compareAndSwapObject(pred, WNEXT, node, succ);
          }
          if (succ != null && (w = succ.thread) != null) {
            succ.thread = null;
            U.unpark(w);       // wake up succ to observe new pred
          }
          if (pred.status != CANCELLED || (pp = pred.prev) == null) {
            break;
          }
          node.prev = pp;        // repeat if new pred wrong/cancelled
          U.compareAndSwapObject(pp, WNEXT, pred, succ);
          pred = pp;
        }
      }
    }
    WNode h; // Possibly release first waiter
    while ((h = whead) != null) {
      long s;
      WNode q; // similar to release() but check eligibility
      if ((q = h.next) == null || q.status == CANCELLED) {
        for (WNode t = wtail; t != null && t != h; t = t.prev) {
          if (t.status <= 0) {
            q = t;
          }
        }
      }
      if (h == whead) {
        if (q != null && h.status == 0 &&
            ((s = state) & ABITS) != WBIT && // waiter is eligible
            (s == 0L || q.mode == RMODE)) {
          release(h);
        }
        break;
      }
    }
    return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
  }

  // Unsafe mechanics
  private static final sun.misc.Unsafe U;
  private static final long STATE;
  private static final long WHEAD;
  private static final long WTAIL;
  private static final long WNEXT;
  private static final long WSTATUS;
  private static final long WCOWAIT;
  private static final long PARKBLOCKER;

  static {
    try {
      U = sun.misc.Unsafe.getUnsafe();
      Class<?> k = StampedLock.class;
      Class<?> wk = WNode.class;
      STATE = U.objectFieldOffset
          (k.getDeclaredField("state"));
      WHEAD = U.objectFieldOffset
          (k.getDeclaredField("whead"));
      WTAIL = U.objectFieldOffset
          (k.getDeclaredField("wtail"));
      WSTATUS = U.objectFieldOffset
          (wk.getDeclaredField("status"));
      WNEXT = U.objectFieldOffset
          (wk.getDeclaredField("next"));
      WCOWAIT = U.objectFieldOffset
          (wk.getDeclaredField("cowait"));
      Class<?> tk = Thread.class;
      PARKBLOCKER = U.objectFieldOffset
          (tk.getDeclaredField("parkBlocker"));

    } catch (Exception e) {
      throw new Error(e);
    }
  }
}
